package com.wkr.leetcode;

import java.util.*;

public class StringLeetCode {

    /**
     * 最长回文串
     *
     * 输入：s = "babad"
     * 输出："bab"
     * 解释："aba" 同样是符合题意的答案。
     */
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;

        // dp[i][j] 表示 s[i, j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        char[] charArray = s.toCharArray();

        // 类似于收缩,不能一直外扩
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i + 1 <= 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }


                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }

            }
        }

        return s.substring(begin, begin + maxLen);
    }

    /**
     * 最长无重复字符串
     */
    public int lengthOfLongestSubstring(String s) {

        int length = s.length();
        int maxLength = length == 0 ? 0 : 1;

        for (int i = 0; i < length; i++) {
            Set<Character> set = new HashSet<>();
            for (int j = i; j < length; j++) {
                if (!set.add(s.charAt(j))) {
                    break;
                }
            }
            if (set.size() > maxLength) {
                maxLength = set.size();
            }
        }
        return maxLength;
    }

    public int lengthOfLongestSubstring2(String s) {

        int[] last = new int[128];
        for(int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int n = s.length();

        int res = 0;
        // 窗口开始位置
        int start = 0;
        for(int i = 0; i < n; i++) {
            int index = s.charAt(i);
            start = Math.max(start, last[index] + 1);
            res   = Math.max(res, i - start + 1);
            last[index] = i;
        }
        return res;
    }

    /**
     * 字符串翻转
     */
    public String reverse(String s) {
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (char c : chars) {
            stack.push(c);
        }
        for (int i = 0; i < chars.length; i++) {
            chars[i] = stack.pop();
        }

        return String.valueOf(chars);
    }


    /**
     * 00*
     * 0*0*
     * *000*
     * 0*0*
     * 00*
     * 打印镂空棱形
     */
    public void printStart(int n) {
        for(int i = 0; i < n; i++){
            int temp = n - 1 - i;
            for(int j = 0; j < temp; j++) {
                System.out.print(" ");
            }
            int temp2 = (i + 1) * 2 - 1;
            for(int j = 0; j < temp2; j++) {
                if(j == 0 || j == temp2 - 1) {
                    System.out.print("*");
                } else {
                    System.out.print(" ");
                }
            }
            System.out.println("");
        }
        for(int i = 0; i < n - 1; i++){
            int temp = 1 + i;
            for(int j = 0; j < temp; j++) {
                System.out.print(" ");
            }
            int temp2 = (n - 1 - i) * 2 - 1;
            for(int j = 0; j < temp2; j++) {
                if(j == 0 || j == temp2 - 1) {
                    System.out.print("*");
                } else {
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
    }

    /**
     * Z 字形变换
     * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
     *
     * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
     *
     * P   A   H   N
     * A P L S I I G
     * Y   I   R
     * 输入：s = "PAYPALISHIRING", numRows = 3
     * 输出："PAHNAPLSIIGYIR"
     * 链接：https://leetcode-cn.com/problems/zigzag-conversion
     */
    public String convert(String s, int numRows) {

        if (s.length() == 1 || numRows == 1) {
            return s;
        }

        int length = s.length();
        List<StringBuilder> rows = new ArrayList<>(numRows);
        for (int i = 0; i < numRows; i++) {
            rows.add(new StringBuilder());
        }
        int x = 0;
        int y = 0;
        for (int i = 0; i < length; i++) {
            rows.get(x).append(s.charAt(i));
            if (y % (numRows - 1) == 0) {
                if (x != numRows - 1) {
                    x++;
                } else {
                    // 回到最低点上一层
                    x = numRows - 2;
                    y++;
                }
            } else {
                x--;
                y++;
            }
        }
        StringBuilder ans = new StringBuilder();
        for(StringBuilder row : rows) ans.append(row);
        return ans.toString();
    }

    /**
     * 匹配字符串
     * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
     *
     * 输入: haystack = "hello", needle = "ll"
     * 输出: 2
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/implement-strstr
     */
    public int sundayStr(String haystack, String needle) {

        if (Objects.isNull(needle) || Objects.isNull(haystack)) {
            return -1;
        }
        // 模式串长度
        int patternLen = needle.length();
        // 目标串长度
        int targetLen = haystack.length();

        if (patternLen > targetLen) {
            return -1;
        }
        if ("".equals(needle)) {
            return 0;
        }

        // 查询索引
        int idx = 0;

        // 偏移表
        // 计算：出现的最右的位置到末尾 + 1 等价于 长度 - 最右出现的索引
        Map<Character, Integer> offset = new HashMap<>(patternLen);
        for (int i = 0; i < patternLen; i++) {
            offset.put(needle.charAt(i), patternLen - i);
        }
        while (idx + patternLen <= targetLen) {
            if (needle.equals(haystack.substring(idx, idx + patternLen))) {
                return idx;
            } else {
                if (patternLen + idx >= targetLen) {
                    break;
                }
                // 当前匹配串后一位字符是不是在模式串中出现过
                if (offset.containsKey(haystack.charAt(patternLen + idx))) {
                    idx = idx + offset.get(haystack.charAt(patternLen + idx));
                } else {
                    idx = idx + patternLen + 1;
                }
            }
        }
        return -1;
    }
    public int strStr(String haystack, String needle) {
        //两种特殊情况
        if (needle.length() == 0) {
            return 0;
        }
        if (haystack.length() == 0) {
            return -1;
        }
        // char 数组
        char[] hasyarr = haystack.toCharArray();
        char[] nearr = needle.toCharArray();
        //长度
        int halen = hasyarr.length;
        int nelen = nearr.length;
        //返回下标
        return kmp(hasyarr,halen,nearr,nelen);

    }
    public int kmp (char[] hasyarr, int halen, char[] nearr, int nelen) {
        //获取next 数组
        int[] next = next(nearr,nelen);
        int j = 0;
        for (int i = 0; i < halen; ++i) {
            //发现不匹配的字符，然后根据 next 数组移动指针，移动到最大公共前后缀的，
            //前缀的后一位,和咱们移动模式串的含义相同
            while (j > 0 && hasyarr[i] != nearr[j]) {
                j = next[j - 1] + 1;
                //超出长度时，可以直接返回不存在
                if (nelen - j + i > halen) {
                    return -1;
                }
            }
            //如果相同就将指针同时后移一下，比较下个字符
            if (hasyarr[i] == nearr[j]) {
                ++j;
            }
            //遍历完整个模式串，返回模式串的起点下标
            if (j == nelen) {
                return i - nelen + 1;
            }
        }
        return -1;
    }

    public  int[] next (char[] needle,int len) {
        //定义 next 数组
        int[] next = new int[len];
        // 初始化
        next[0] = -1;
        int k = -1;
        for (int i = 1; i < len; ++i) {
            //我们此时知道了 [0,i-1]的最长前后缀，但是k+1的指向的值和i不相同时，我们则需要回溯
            //因为 next[k]就时用来记录子串的最长公共前后缀的尾坐标（即长度）
            //就要找 k+1前一个元素在next数组里的值,即next[k+1]
            while (k != -1 && needle[k + 1] != needle[i]) {
                k = next[k];
            }
            // 相同情况，就是 k的下一位，和 i 相同时，此时我们已经知道 [0,i-1]的最长前后缀
            //然后 k - 1 又和 i 相同，最长前后缀加1，即可
            if (needle[k+1] == needle[i]) {
                ++k;
            }
            next[i] = k;

        }
        return next;
    }


    /**
     * 查找最后一个单词的长度
     */
    public int lengthOfLastWord(String s) {
        int end = s.length() - 1;
        while(end >= 0 && s.charAt(end) == ' ') end--;
        if(end < 0) return 0;
        int start = end;
        while(start >= 0 && s.charAt(start) != ' ') start--;
        return end - start;
    }
}
